package com.lwl.Algorithmic_data_structure.堆与堆排序.mycode;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 给出一个多个整数起始线段的数组
 *
 * 返回重复线段最多的线段区域所有的线段数量  ,  其中 [1,3] 与 [3,5] 之间没有重合区域
 */
public class MaxLinesCover {

    static class Line{
        private int start;
        private int end;

        public Line(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    public static int maxLinesCover(int[][] m){
        if (m == null || m.length <= 0)
        {
            return 0;
        }

        Line[] lines = new Line[m.length];

        for (int i = 0; i < m.length; i++) {
            lines[i] = new Line(m[i][0],m[i][1]);
        }

        Arrays.sort(lines, (o1, o2) -> o1.start - o2.start);

        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        int max = 0;

        for (int i = 0; i < lines.length; i++)
        {
            //保持容器中的线段都是重叠的，只需要使用最小堆保存线段的末尾
            //并保证最小的末尾也比当前线段的起点大即可
            while (!minHeap.isEmpty() && minHeap.peek() <= lines[i].start)
            {
                minHeap.poll();
            }
            minHeap.add(lines[i].end);
            max = Math.max(max,minHeap.size());
        }
        return max;
    }

}
